/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 62536
 * Date: 2024-05-30
 * Time: 10:32
 */
public class Solution {
    //三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。
    // 实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
    public int waysToStep(int n) {
        int Mod = (int)1e9 + 7;

        if(n == 1 || n == 2){
            return n;
        }
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for(int i = 4; i < n+1; i++){
            dp[i] = ((dp[i-1] + dp[i-2]) % Mod + dp[i-3]) %Mod;
        }
        return dp[n];
    }
}
